package leetcode.newcoder;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by tiang on 2018/8/9.
 给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。
 输入描述:
 第一行包含两个整数n,m.

 第二行给出n个整数A1，A2，...，An。

 数据范围

 对于30%的数据，1 <= n, m <= 1000

 对于100%的数据，1 <= n, m, Ai <= 10^5


 输出描述:
 输出仅包括一行，即所求的答案
 */
public class XOR {
    /**
     * 最高AC 80
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),
                m = scanner.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
            nums[i] = scanner.nextInt();

        System.out.println(XORGreater(nums, m));
    }

    private static long XORGreater(int[] nums, int aim){
        Arrays.sort(nums);
        int[] digits = new int[nums.length];
        for(int i=0;i<digits.length;i++)
            digits[i] = numOfDigits(nums[i]);
        // 目标数字的位数
        int aimDigit = numOfDigits(aim);
        long count = 0;
        for(int i=0;i<nums.length;i++){
            // 当前元素的位数
            int nowDigit = digits[i];
            if(nowDigit<aimDigit)
                continue;
            else if(nowDigit == aimDigit){
                // 从下向上查找
                int j=0;
                while(j<i && digits[j]<digits[i]){
                    if((nums[j]^nums[i]) > aim)
                        count++;
                    j++;
                }
            }else{
                // 如果当前值的位数比目标位数大，那么只有跟与自己位数相同的人进行异或操作才有可能结果小于预期
                int j = i-1;
                // 判断跟自己位数相同的数字异或结果是否符合要求
                while(j >= 0 && digits[j] == nowDigit){
                    if((nums[j]^nums[i]) > aim)
                        count++;
                    j--;
                }
                count += j+1;
            }
        }
        return count;
    }

    /**
     * 判断一个数的二进制有几位
     * @param num
     * @return
     */
    private static int numOfDigits(int num){
        int count = 0;
        while(num!=0){
            num >>= 1;
            count++;
        }
        return count;
    }
}
